package cn.chen.数据结构.二叉树.赫夫曼树;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 赫夫曼树：树的带权路径最小的树（WPL）  树的带权路径=叶结点带权路径长度之和  结点带权路径长度=路径长度*结点的权
 */
public class HuffmanTree {

    // 创建赫夫曼树的方法
    /**
     * @param a     要创建赫夫曼树的数组
     * @return      创建好的赫夫曼树的根结点
     */
    public HuffmanNode createHuffmanTree(int []a ){

        List<HuffmanNode> nodes=new ArrayList<>();

        // 将数组中的数都存放到HuffmanNode节点中
        for(int i:a)
            nodes.add(new HuffmanNode(i));

        while(nodes.size()>1) { // 每次循环处理两个 ，添加一个新节点，最终集合中只有一个元素的时候就是处理完了
            // 排序
            Collections.sort(nodes);

            // 取出第一个元素 和第二个元素
            HuffmanNode leftNode = nodes.get(0);
            HuffmanNode rightNode = nodes.get(1);

            // 创建一个新的结点，权值为两个结点的权值之和
            HuffmanNode parent = new HuffmanNode(leftNode.value + rightNode.value);
            parent.left=leftNode;
            parent.right=rightNode;

            // 删除使用过的结点
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            // 将新节点加入到集合中
            nodes.add(parent);
        }
        // 循环结束之后，集合中只有唯一一个节点，而且该节点就是赫夫曼树的根结点
        return nodes.get(0);
    }

    // 前序遍历
    public void preOrder(HuffmanNode node){

        if(node==null)
            return;

        if(node.left==null&&node.right==null)   // 判断是否是叶子节点，只有叶子节点才是赫夫曼树的节点，我们才输出
            System.out.println(node);

        preOrder(node.left);
        preOrder(node.right);
    }

}
